package leetcode.code1850;

import java.io.UnsupportedEncodingException;
import java.util.Arrays;
import java.util.Random;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	public int getMinSwaps(String num, int k) {
		char[] nums = num.toCharArray();
		// 找到最近的第k大
		while (k > 0) {
			next_permutation(nums);
			k--;
		}
		// 从num变成n需要几步
		return ff(num.toCharArray(), nums);
	}

	private int ff(char[] from, char[] to) {
		int ans = 0;
		for (int i = 0; i < to.length; i++) {
			if (from[i] == to[i]) {// 一样的不需要变
				continue;
			}
			int j = i + 1;
			for (; j < to.length && to[i] != from[j]; j++) {// 找到最近一个一样的

			}
			for (int k = j; k > i; k--) {// 一个一个搬过来
				ans++;
				this.swap(from, k, k - 1);
			}
		}
		return ans;
	}

	public void next_permutation(char[] nums) {
		int i = nums.length - 2;
		while (i >= 0 && nums[i] >= nums[i + 1]) {
			i--;
		}
		if (i >= 0) {
			int j = nums.length - 1;
			while (j >= 0 && nums[i] >= nums[j]) {
				j--;
			}
			swap(nums, i, j);
		}
		Arrays.parallelSort(nums, i + 1, nums.length); // 后面排序
	}

	private void swap(char[] cs, int i, int j) {
		char tmp = cs[i];
		cs[i] = cs[j];
		cs[j] = tmp;
	}

	@Override
	public void debug4() {
		// 954368
		// 954863
		// 954386
		H.compare(5, this.getMinSwaps("948635", 64));
		H.compare(3, this.getMinSwaps("059", 5));
		H.compare(4, this.getMinSwaps("11112", 4));
		H.compare(2, this.getMinSwaps("5489355142", 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) throws UnsupportedEncodingException {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < 120; i++) {
			byte[] b = new byte[] { Integer.valueOf(176 + (int) (Math.random() * 39)).byteValue(),
					 Integer.valueOf(161 + (int) (Math.random() * 93)).byteValue() };
			sb.append(new String(b, "GBK"));
		}
		System.out.println(sb.toString());
	}

}
